Warum ist die Verarbeitung eines sortierten Arrays schneller als die Verarbeitung eines unsortierten Arrays?

Sie sind ein Opfer des Fehlschlags der Zweigvorhersage.
Was ist Zweigvorhersage?
Betrachten Sie einen Eisenbahnknotenpunkt:
Bild von Mecanismo, über Wikimedia Commons. Wird unter der CC-By-SA 3.0-Lizenz verwendet.
Nehmen wir zum Zwecke der Argumentation an, dass dies im 19. Jahrhundert war - vor Ferngesprächen oder Funkkommunikation.
Sie sind der Betreiber einer Kreuzung und hören einen Zug kommen. Sie haben keine Ahnung, in welche Richtung es gehen soll. Sie halten den Zug an, um den Fahrer zu fragen, in welche Richtung er möchte. Und dann stellen Sie den Schalter entsprechend ein.
Züge sind schwer und haben viel Trägheit. Es dauert also ewig, bis sie anfangen und langsamer werden.
Gibt es einen besseren Weg? Sie raten, in welche Richtung der Zug fahren wird!
Wenn Sie richtig geraten haben, geht es weiter.
Wenn Sie falsch geraten haben, hält der Kapitän an, fährt zurück und schreit Sie an, um den Schalter umzulegen. Dann kann es auf dem anderen Pfad neu starten.
Wenn Sie jedes Mal richtig raten, muss der Zug niemals anhalten. Wenn Sie zu oft falsch raten, verbringt der Zug viel Zeit damit, anzuhalten, zu sichern und neu zu starten.
Betrachten Sie eine if-Anweisung: Auf Prozessorebene handelt es sich um eine Verzweigungsanweisung:
Sie sind ein Prozessor und sehen einen Zweig. Sie haben keine Ahnung, in welche Richtung es gehen wird. Wie geht's? Sie stoppen die Ausführung und warten, bis die vorherigen Anweisungen vollständig sind. Dann gehen Sie den richtigen Weg weiter.
Moderne Prozessoren sind kompliziert und haben lange Pipelines. Sie brauchen also ewig, um sich aufzuwärmen und zu verlangsamen.
Gibt es einen besseren Weg? Sie raten, in welche Richtung der Zweig gehen wird!
Wenn Sie richtig geraten haben, fahren Sie mit der Ausführung fort.
Wenn Sie falsch geraten haben, müssen Sie die Pipeline spülen und zum Zweig zurückrollen. Dann können Sie den anderen Pfad neu starten.
Wenn Sie jedes Mal richtig raten, muss die Ausführung niemals aufhören. Wenn Sie zu oft falsch raten, verbringen Sie viel Zeit damit, anzuhalten, zurückzurollen und neu zu starten.
Dies ist eine Verzweigungsvorhersage. Ich gebe zu, es ist nicht die beste Analogie, da der Zug die Richtung nur mit einer Flagge signalisieren könnte. Bei Computern weiß der Prozessor jedoch bis zum letzten Moment nicht, in welche Richtung ein Zweig gehen wird.
Wie würden Sie strategisch raten, um die Häufigkeit zu minimieren, mit der der Zug den anderen Weg zurücklegen und hinunterfahren muss? Sie schauen auf die Vergangenheit! Wenn der Zug 99% der Zeit nach links fährt, raten Sie nach links. Wenn es sich abwechselt, wechseln Sie Ihre Vermutungen. Wenn es alle drei Male in eine Richtung geht, raten Sie dasselbe ...
Mit anderen Worten, Sie versuchen, ein Muster zu identifizieren und ihm zu folgen. So funktionieren Zweigprädiktoren mehr oder weniger.
Die meisten Anwendungen haben gut erzogene Zweige. Moderne Branchenprädiktoren erzielen daher in der Regel Trefferquoten von> 90%. Bei unvorhersehbaren Verzweigungen ohne erkennbare Muster sind Verzweigungsvorhersagen jedoch praktisch nutzlos.
Weiterführende Literatur: Artikel "Branch Predictor" auf Wikipedia.
Wie von oben angedeutet, ist der Schuldige diese if-Aussage:
if (Daten [c]> = 128)
Summe + = Daten [c];
Beachten Sie, dass die Daten gleichmäßig zwischen 0 und 255 verteilt sind. Wenn die Daten sortiert werden, wird ungefähr die erste Hälfte der Iterationen nicht in die if-Anweisung eingegeben. Danach geben alle die if-Anweisung ein.
Dies ist für den Zweigprädiktor sehr freundlich, da der Zweig viele Male nacheinander in dieselbe Richtung geht. Selbst ein einfacher Sättigungszähler sagt den Zweig bis auf die wenigen Iterationen nach dem Richtungswechsel korrekt voraus.
Schnelle Visualisierung:
T = Zweig genommen
N = Zweig nicht genommen
Daten [] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
Zweig = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (leicht vorherzusagen)
Wenn die Daten jedoch vollständig zufällig sind, wird der Verzweigungsprädiktor unbrauchbar, da er keine zufälligen Daten vorhersagen kann. Somit wird es wahrscheinlich eine Fehleinschätzung von etwa 50% geben (nicht besser als zufälliges Erraten).
Daten [] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
Zweig = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (völlig zufällig - schwer vorherzusagen)
Was kann also getan werden?
Wenn der Compiler den Zweig nicht in eine bedingte Verschiebung optimieren kann, können Sie einige Hacks versuchen, wenn Sie bereit sind, die Lesbarkeit für die Leistung zu opfern.
Ersetzen:
if (Daten [c]> = 128)
Summe + = Daten [c];
mit:
int t = (Daten [c] - 128) >> 31;
Summe + = ~ t & Daten [c];
Dies eliminiert den Zweig und ersetzt ihn durch einige bitweise Operationen.
(Beachten Sie, dass dieser Hack nicht unbedingt der ursprünglichen if-Anweisung entspricht. In diesem Fall gilt er jedoch für alle Eingabewerte von data [].)
Benchmarks: Core i7 920 bei 3,5 GHz
C ++ - Visual Studio 2010 - x64-Version
// Branch - Random
Sekunden = 11,777
// Branch - Sortiert
Sekunden = 2,352
// Branchless - Zufällig
Sekunden = 2,564
// Branchless - Sortiert
Sekunden = 2,587
Java - NetBeans 7.1.1 JDK 7 - x64
// Branch - Random
Sekunden = 10,93293813
// Branch - Sortiert
Sekunden = 5,643797077
// Branchless -Zufällig
Sekunden = 3,113581453
// Branchless - Sortiert
Sekunden = 3,186068823
Beobachtungen:
Mit der Verzweigung: Es gibt einen großen Unterschied zwischen sortierten und unsortierten Daten.
Mit dem Hack: Es gibt keinen Unterschied zwischen sortierten und unsortierten Daten.
Im C ++ - Fall ist der Hack tatsächlich etwas langsamer als beim Verzweigen, wenn die Daten sortiert werden.
Eine allgemeine Faustregel besteht darin, eine datenabhängige Verzweigung in kritischen Schleifen (wie in diesem Beispiel) zu vermeiden.
Aktualisieren:
GCC 4.6.1 mit -O3 oder -ftree-vectorize auf x64 kann eine bedingte Verschiebung erzeugen. Es gibt also keinen Unterschied zwischen sortierten und unsortierten Daten - beide sind schnell.
(Oder etwas schnell: Für den bereits sortierten Fall kann cmov langsamer sein, insbesondere wenn GCC es auf den kritischen Pfad setzt, anstatt nur hinzuzufügen, insbesondere bei Intel vor Broadwell, wo cmov eine Latenz von 2 Zyklen aufweist: Das gcc-Optimierungsflag -O3 verlangsamt den Code als -O2)
VC ++ 2010 kann selbst unter / Ox keine bedingten Verschiebungen für diesen Zweig generieren.
Intel C ++ Compiler (ICC) 11 macht etwas Wunderbares. Es vertauscht die beiden Schleifen und hebt dadurch den unvorhersehbaren Zweig zur äußeren Schleife. Es ist also nicht nur immun gegen falsche Vorhersagen, sondern auch doppelt so schnell wie alles, was VC ++ und GCC erzeugen können! Mit anderen Worten, ICC nutzte die Testschleife, um den Benchmark zu besiegen ...
Wenn Sie dem Intel-Compiler den verzweigungslosen Code geben, vektorisiert er ihn einfach nach rechts ... und ist genauso schnell wie bei der Verzweigung (mit dem Schleifenaustausch).
Dies zeigt, dass selbst ausgereifte moderne Compiler in ihrer Fähigkeit, Code zu optimieren, sehr unterschiedlich sein können ...
|
Verzweigungsvorhersage.
Bei einem sortierten Array sind die Bedingungsdaten [c]> = 128 zuerst für einen Wertestreifen falsch und werden dann für alle späteren Werte wahr. Das ist leicht vorherzusagen. Bei einem unsortierten Array zahlen Sie die Verzweigungskosten.
|
Der Grund, warum sich die Leistung beim Sortieren der Daten drastisch verbessert, besteht darin, dass die Strafe für die Verzweigungsvorhersage entfernt wird, wie in der Antwort von Mysticial ausführlich erläutert.
Nun, wenn wir uns den Code ansehen
if (Daten [c]> = 128)
Summe + = Daten [c];
Wir können feststellen, dass die Bedeutung dieses speziellen Zweigs, wenn ... sonst ... darin besteht, etwas hinzuzufügen, wenn eine Bedingung erfüllt ist. Diese Art von Verzweigung kann leicht in eine bedingte Verschiebungsanweisung umgewandelt werden, die in einem x86-System in eine bedingte Verschiebungsanweisung kompiliert wird: cmovl. Die Verzweigung und damit die mögliche Verzweigungsvorhersagestrafe wird entfernt.
In C, also C ++, ist die Anweisung, die direkt (ohne Optimierung) in die bedingte Verschiebungsanweisung in x86 kompiliert werden würde, der ternäre Operator ...? ...: .... Also schreiben wir die obige Aussage in eine äquivalente um:
Summe + = Daten [c]> = 128? Daten [c]: 0;
Unter Beibehaltung der Lesbarkeit können wir den Beschleunigungsfaktor überprüfen.
Auf einem Intel Core i7-2600K mit 3,4 GHz und Visual Studio 2010 Release-Modus lautet der Benchmark (Format von Mysticial kopiert):
x86
// Branch - Random
Sekunden = 8,885
// Branch - Sortiert
Sekunden = 1,528
// Branchless - Zufällig
Sekunden = 3,716
// Branchless - Sortiert
Sekunden = 3,71
x64
// Branch - Random
Sekunden = 11.302
// Branch - Sortiert
Sekunden = 1,830
// Branchless - Zufällig
Sekunden = 2,736
// Branchless - Sortiert
Sekunden = 2,737
Das Ergebnis ist in mehreren Tests robust. Wir erhalten eine große Beschleunigung, wenn das Verzweigungsergebnis nicht vorhersehbar ist, aber wir leiden ein wenig, wenn es vorhersehbar ist. Wenn Sie eine bedingte Verschiebung verwenden, ist die Leistung unabhängig vom Datenmuster gleich.
Schauen wir uns nun die von ihnen generierte x86-Assembly genauer an. Der Einfachheit halber verwenden wir zwei Funktionen max1 und max2.
max1 verwendet den bedingten Zweig, wenn ... sonst ...:
int max1 (int a, int b) {
wenn (a> b)
return a;
sonst
return b;
}}
max2 verwendet den ternären Operator ...? ...: ...:
int max2 (int a, int b) {
a> b zurückgeben? a: b;
}}
Auf einem x86-64-Computer generiert GCC -S die folgende Baugruppe.
: max1
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl -8 (% rbp),% eax
jle .L2
movl -4 (% rbp),% eax
movl% eax, -12 (% rbp)
jmp .L4
.L2:
movl -8 (% rbp),% eax
movl% eax, -12 (% rbp)
.L4:
movl -12 (% rbp),% eax
verlassen
ret
: max2
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl% eax, -8 (% rbp)
cmovge -8 (% rbp),% eax
verlassen
ret
max2 verwendet aufgrund der Verwendung der Anweisung cmovge viel weniger Code. Der eigentliche Vorteil ist jedoch, dass max2 keine Verzweigungssprünge (jmp) beinhaltet, die einen erheblichen Leistungsverlust bedeuten würden, wenn das vorhergesagte Ergebnis nicht stimmt.
Warum ist eine bedingte Bewegung besser?
In einem typischen x86-Prozessor ist die Ausführung eines Befehls in mehrere Stufen unterteilt. Wir haben ungefähr unterschiedliche Hardware, um mit verschiedenen Phasen fertig zu werden. Wir müssen also nicht warten, bis eine Anweisung abgeschlossen ist, um eine neue zu starten. Dies wird als Pipelining bezeichnet.
In einem Verzweigungsfall wird die folgende Anweisung durch die vorhergehende bestimmt, sodass wir kein Pipelining durchführen können. Wir müssen entweder warten oder vorhersagen.
In einem bedingten VerschiebungsfallDer ausführungsbedingte Verschiebungsbefehl ist in mehrere Stufen unterteilt, aber die früheren Stufen wie Abrufen und Dekodieren hängen nicht vom Ergebnis des vorherigen Befehls ab. nur letztere Stufen brauchen das Ergebnis. Wir warten also einen Bruchteil der Ausführungszeit eines Befehls. Aus diesem Grund ist die Version für bedingte Verschiebungen langsamer als der Zweig, wenn die Vorhersage einfach ist.
Das Buch Computersysteme: Die Perspektive eines Programmierers, zweite Ausgabe, erklärt dies ausführlich. Sie können Abschnitt 3.6.6 für Anweisungen zum bedingten Verschieben, das gesamte Kapitel 4 für die Prozessorarchitektur und Abschnitt 5.11.2 für die Sonderbehandlung für Zweigvorhersage- und Fehlvorhersage-Strafen überprüfen.
Manchmal können einige moderne Compiler unseren Code für Assemblierungen mit besserer Leistung optimieren, manchmal können einige Compiler dies nicht (der betreffende Code verwendet den nativen Compiler von Visual Studio). Wenn wir den Leistungsunterschied zwischen einem Zweig und einer bedingten Verschiebung kennen, wenn dies nicht vorhersehbar ist, können wir Code mit besserer Leistung schreiben, wenn das Szenario so komplex wird, dass der Compiler sie nicht automatisch optimieren kann.
|
Wenn Sie neugierig auf weitere Optimierungen sind, die an diesem Code vorgenommen werden können, beachten Sie Folgendes:
Beginnend mit der ursprünglichen Schleife:
für (vorzeichenloses i = 0; i <100000; ++ i)
{
für (vorzeichenloses j = 0; j  = 128)
Summe + = Daten [j];
}}
}}
Mit dem Schleifenaustausch können wir diese Schleife sicher ändern in:
für (vorzeichenloses j = 0; j  = 128)
Summe + = Daten [j];
}}
}}
Dann können Sie sehen, dass die if-Bedingung während der Ausführung der i-Schleife konstant ist, sodass Sie die if-out-Funktion hochziehen können:
für (vorzeichenloses j = 0; j  = 128)
{
für (vorzeichenloses i = 0; i <100000; ++ i)
{
Summe + = Daten [j];
}}
}}
}}
Dann sehen Sie, dass die innere Schleife zu einem einzigen Ausdruck zusammengefasst werden kann, sofern das Gleitkommamodell dies zulässt (/ fp: fast wird beispielsweise ausgelöst).
für (vorzeichenloses j = 0; j  = 128)
{
Summe + = Daten [j] * 100000;
}}
}}
Dieser ist 100.000 Mal schneller als zuvor.
|
Zweifellos wären einige von uns daran interessiert, Code zu identifizieren, der für den Verzweigungsprädiktor der CPU problematisch ist. Der Valgrind-Tool-Cachegrind verfügt über einen Branch-Predictor-Simulator, der mithilfe des Flags --branch-sim = yes aktiviert wird. Wenn Sie die Beispiele in dieser Frage übergehen, wobei die Anzahl der äußeren Schleifen auf 10000 reduziert und mit g ++ kompiliert wurde, erhalten Sie folgende Ergebnisse:
Sortiert:
== 32551 == Zweige: 656.645.130 (656.609.208 cond + 35.922 ind)
== 32551 == Fehlvorhersagen: 169.556 (169.095 cond + 461 ind)
== 32551 == Falschpreisrate: 0,0% (0,0% + 1,2%)
Unsortiert:
== 32555 == Zweige: 655.996.082 (655.960.160 cond + 35.922 ind)
== 32555 == Fehlvorhersagen: 164.073.152 (164.072.692 cond + 460 ind)
== 32555 == Falsche Rate: 25,0% (25,0% + 1,2%)
Wir gehen auf die zeilenweise Ausgabe von cg_annotate ein, die wir für die betreffende Schleife sehen:
Sortiert:
Bc Bcm Bi Bim
10.001 4 0 0 für (vorzeichenloses i = 0; i <10000; ++ i)
. . . . {
. . . . // primäre Schleife
327,690,000 10,016 0 0 für (vorzeichenloses c = 0; c  = 128)
0 0 0 0 Summe + = Daten [c];
. . . . }}
. . . . }}
Unsortiert:
Bc Bcm Bi Bim
10.001 4 0 0 für (vorzeichenloses i = 0; i <10000; ++ i)
. . . . {
. . . . // primäre Schleife
327,690,000 10,038 0 0 für (vorzeichenloses c = 0; c  = 128)
0 0 0 0 Summe + = Daten [c];
. . . . }}
. . . . }}
Auf diese Weise können Sie die problematische Zeile leicht identifizieren. In der unsortierten Version verursacht die Zeile if (data [c]> = 128) 164.050.007 falsch vorhergesagte bedingte Verzweigungen (Bcm) unter dem Verzweigungsvorhersagemodell von cachegrind, während sie in der sortierten Version nur 10.006 verursacht .
Alternativ können Sie unter Linux das Subsystem für Leistungsindikatoren verwenden, um dieselbe Aufgabe auszuführen, jedoch mit nativer Leistung unter Verwendung von CPU-Leistungsindikatoren.
perf stat ./sumtest_sorted
Sortiert:
Leistungsindikatorstatistiken für './sumtest_sorted':
11808.095776 Task-Clock # 0.998 CPUs verwendet
1.062 Kontextschalter # 0,090 K / s
14 CPU-Migrationen # 0,001 K / Sek
337 Seitenfehler # 0,029 K / Sek
26.487.882.764 Zyklen # 2.243 GHz
41.025.654.322 Anweisungen # 1.55 Insns pro Zyklus
6.558.871.379 Zweige # 555.455 M / s
567.204 Filialfehler # 0,01% aller Filialen
11.827228330 Sekunden verstrichene Zeit
Unsortiert:
PerformanceZählerstatistiken für './sumtest_unsorted':
28877.954344 Task-Clock # 0.998 Verwendete CPUs
2.584 Kontextschalter # 0,089 K / s
18 CPU-Migrationen # 0,001 K / Sek
335 Seitenfehler # 0,012 K / Sek
65.076.127.595 Zyklen # 2.253 GHz
41.032.528.741 Anweisungen # 0.63 Insns pro Zyklus
6,560,579,013 Zweige # 227,183 M / s
1.646.394.749 Filialfehler # 25,10% aller Filialen
28.935500947 Sekunden verstrichene Zeit
Es kann auch Quellcode-Annotationen mit Demontage durchführen.
perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
Prozent | Quellcode & Demontage von sumtest_unsorted
------------------------------------------------
...
: Summe + = Daten [c];
0,00: 400a1a: mov -0x14 (% rbp),% eax
39,97: 400a1d: mov% eax,% eax
5,31: 400a1f: mov -0x20040 (% rbp,% rax, 4),% eax
4,60: 400a26: cltq
0,00: 400a28:% rax, -0x30 (% rbp) hinzufügen
...
Weitere Informationen finden Sie im Performance-Tutorial.
|
Ich habe gerade diese Frage und ihre Antworten gelesen und habe das Gefühl, dass eine Antwort fehlt.
Ein üblicher Weg, um die Verzweigungsvorhersage zu eliminieren, die in verwalteten Sprachen besonders gut funktioniert, ist die Tabellensuche anstelle der Verwendung einer Verzweigung (obwohl ich sie in diesem Fall nicht getestet habe).
Dieser Ansatz funktioniert im Allgemeinen, wenn:
Es ist eine kleine Tabelle und wird wahrscheinlich im Prozessor zwischengespeichert
Sie führen die Dinge in einer ziemlich engen Schleife aus und / oder der Prozessor kann die Daten vorladen.
Hintergrund und warum
Aus Prozessorsicht ist Ihr Speicher langsam. Um den Geschwindigkeitsunterschied auszugleichen, sind in Ihrem Prozessor einige Caches integriert (L1 / L2-Cache). Stellen Sie sich also vor, Sie führen Ihre netten Berechnungen durch und stellen fest, dass Sie ein Stück Speicher benötigen. Der Prozessor erhält seine 'Lade'-Operation und lädt den Speicher in den Cache - und verwendet dann den Cache, um den Rest der Berechnungen durchzuführen. Da der Speicher relativ langsam ist, verlangsamt dieses "Laden" Ihr Programm.
Wie bei der Verzweigungsvorhersage wurde dies bei den Pentium-Prozessoren optimiert: Der Prozessor sagt voraus, dass ein Datenelement geladen werden muss, und versucht, diese in den Cache zu laden, bevor die Operation tatsächlich den Cache erreicht. Wie wir bereits gesehen haben, geht die Verzweigungsvorhersage manchmal furchtbar schief - im schlimmsten Fall müssen Sie zurückgehen und tatsächlich auf eine Speicherauslastung warten, die ewig dauern wird (mit anderen Worten: Eine fehlgeschlagene Verzweigungsvorhersage ist schlecht, ein Speicher Laden nach einem Fehlschlagen der Verzweigungsvorhersage ist einfach schrecklich!).
Glücklicherweise lädt der Prozessor das Speicherzugriffsmuster, wenn es vorhersehbar ist, in seinen schnellen Cache und alles ist in Ordnung.
Das erste, was wir wissen müssen, ist, was klein ist? Während kleiner im Allgemeinen besser ist, gilt als Faustregel, dass Sie sich an Nachschlagetabellen mit einer Größe von <= 4096 Byte halten. Als Obergrenze: Wenn Ihre Nachschlagetabelle größer als 64 KB ist, lohnt es sich wahrscheinlich, sie zu überdenken.
Eine Tabelle erstellen
Wir haben also herausgefunden, dass wir einen kleinen Tisch erstellen können. Als nächstes müssen Sie eine Suchfunktion einrichten. Suchfunktionen sind normalerweise kleine Funktionen, die einige grundlegende Ganzzahloperationen verwenden (und / oder xor verschieben, hinzufügen, entfernen und möglicherweise multiplizieren). Sie möchten, dass Ihre Eingabe von der Suchfunktion in eine Art "eindeutigen Schlüssel" in Ihrer Tabelle übersetzt wird, der Ihnen dann einfach die Antwort auf alle gewünschten Arbeiten gibt.
In diesem Fall bedeutet> = 128, dass wir den Wert behalten können, <128 bedeutet, dass wir ihn loswerden. Der einfachste Weg, dies zu tun, ist die Verwendung eines 'UND': Wenn wir es behalten, UND UND mit 7FFFFFFF; Wenn wir es loswerden wollen, UND wir es mit 0. Beachten Sie auch, dass 128 eine Potenz von 2 ist - also können wir eine Tabelle mit 32768/128 ganzen Zahlen erstellen und sie mit einer Null und viel füllen 7FFFFFFFF's.
Verwaltete Sprachen
Sie fragen sich vielleicht, warum dies in verwalteten Sprachen gut funktioniert. Schließlich überprüfen verwaltete Sprachen die Grenzen der Arrays mit einem Zweig, um sicherzustellen, dass Sie nichts falsch machen ...
Na ja, nicht genau ... :-)
Es wurde ziemlich viel daran gearbeitet, diesen Zweig für verwaltete Sprachen zu entfernen. Zum Beispiel:
für (int i = 0; i  = 128)? c: 0;
}}
// Prüfung
DateTime startTime = System.DateTime.Now;
lange Summe = 0;
für (int i = 0; i <100000; ++ i)
{
// Primärschleife
für (int j = 0; j  = 128. Das heißt, wir können leicht ein einzelnes Bit extrahieren, das uns sagt, ob wir einen Wert wollen oder nicht: durch Verschieben Bei den Daten rechts von 7 Bit bleibt uns ein 0-Bit oder ein 1-Bit übrig, und wir möchten den Wert nur hinzufügen, wenn wir ein 1-Bit haben. Nennen wir dieses Bit das "Entscheidungsbit".
Indem wir den 0/1-Wert des Entscheidungsbits als Index für ein Array verwenden, können wir Code erstellen, der gleich schnell ist, unabhängig davon, ob die Daten sortiert sind oder nicht. Unser Code fügt immer einen Wert hinzu, aber wenn das Entscheidungsbit 0 ist, fügen wir den Wert an einer Stelle hinzu, die uns egal ist. Hier ist der Code:
// Prüfung
clock_t start = clock ();
lang lang a [] = {0, 0};
lange lange Summe;
für (vorzeichenloses i = 0; i <100000; ++ i)
{
// Primärschleife
für (vorzeichenloses c = 0; c > 7);
a [j] + = Daten [c];
}}
}}
double elapsedTime = static_cast  (clock () - start) / CLOCKS_PER_SEC;
Summe = a [1];
Dieser Code verschwendet die Hälfte der Adds, hat jedoch nie einen Fehler bei der Verzweigungsvorhersage. Bei zufälligen Daten ist es enorm schneller als bei der Version mit einer tatsächlichen if-Anweisung.
In meinen Tests war eine explizite Nachschlagetabelle jedoch etwas schneller als diese, wahrscheinlich weil die Indizierung in eine Nachschlagetabelle etwas schneller war als die Bitverschiebung. Dies zeigt, wie mein Code die Nachschlagetabelle einrichtet und verwendet (im Code einfallslos lut für "LookUp Table" genannt). Hier ist der C ++ - Code:
// Deklariere und fülle dann die Nachschlagetabelle aus
int lut [256];
für (vorzeichenloses c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Verwenden Sie die Nachschlagetabelle, nachdem sie erstellt wurde
für (vorzeichenloses i = 0; i <100000; ++ i)
{
// Primärschleife
für (vorzeichenloses c = 0; c  Wert)
node = node-> pLeft;
sonst
node = node-> pRight;
Diese Bibliothek würde so etwas tun wie:
i = (x  Wert);
Knoten = Knoten-> Link [i];
Hier ist ein Link zu diesem Code: Red Black Trees, Eternally Confuzzled
|
Im sortierten Fall können Sie es besser machen, als sich auf eine erfolgreiche Verzweigungsvorhersage oder einen verzweigungslosen Vergleichstrick zu verlassen: Entfernen Sie die Verzweigung vollständig.
In der Tat ist das Array in einer zusammenhängenden Zone mit Daten <128 und einer anderen mit Daten> = 128 partitioniert. Sie sollten also den Partitionspunkt mit einer dichotomischen Suche (unter Verwendung von Lg (arraySize) = 15 Vergleichen) finden und dann eine direkte Akkumulation von durchführen dieser Punkt.
So etwas wie (nicht markiert)
int i = 0, j, k = arraySize;
während (i > 1;
if (Daten [j]> = 128)
k = j;
sonst
i = j;
}}
Summe = 0;
für (; i > 1;
für (i = 0, k = arraySize; i  = 128? k: i) = j)
j = (i + k) >> 1;
für (sum = 0; i  = 128)
/ \.
/ \.
/ \.
wahr falsch
/ \.
/ \.
/ \.
/ \.
B) Summe + = Daten [c]; C) für Schleife oder Druck ().
Ohne Verzweigungsvorhersage würde Folgendes auftreten:
Um Befehl B oder Befehl C auszuführen, muss der Prozessor warten, bis der Befehl A nicht bis zur EX-Stufe in der Pipeline gelangt, da die Entscheidung, zu Befehl B oder Befehl C zu gehen, vom Ergebnis von Befehl A abhängt wird so aussehen.
Wenn if-Bedingung true zurückgibt:
Wann, wenn die Bedingung false zurückgibt:
Infolge des Wartens auf das Ergebnis von Befehl A beträgt die Gesamtmenge der im obigen Fall verbrachten CPU-Zyklen (ohne Verzweigungsvorhersage; sowohl für wahr als auch für falsch) 7.
Was ist also eine Zweigvorhersage?
Der Zweigprädiktor wird versuchen zu erraten, in welche Richtung ein Zweig (eine Wenn-Dann-Sonst-Struktur) gehen wird, bevor dies sicher bekannt ist. Es wird nicht darauf warten, dass die Anweisung A die EX-Stufe der Pipeline erreicht, sondern die Entscheidung erraten und zu dieser Anweisung übergehen (B oder C in unserem Beispiel).
Im Falle einer korrekten Vermutung sieht die Pipeline ungefähr so ​​aus:
Wenn später festgestellt wird, dass die Vermutung falsch war, werden die teilweise ausgeführten Anweisungen verworfen und die Pipeline beginnt mit der richtigen Verzweigung von vorne, was zu einer Verzögerung führt.
Die Zeit, die im Falle einer Verzweigungsfehlvorhersage verschwendet wird, entspricht der Anzahl der Stufen in der Pipeline von der Abrufstufe zur Ausführungsstufe. Moderne Mikroprozessoren neigen dazu, ziemlich lange Pipelines zu haben, so dass die Fehlvorhersageverzögerung zwischen 10 und 20 Taktzyklen liegt. Je länger die Pipeline ist, desto größer ist der Bedarf an einem guten Verzweigungsprädiktor.
Im OP-Code verfügt der Verzweigungsprädiktor zum ersten Mal, wenn die Bedingung erfüllt ist, über keine Informationen, um die Vorhersage zu stützen. Daher wählt er beim ersten Mal zufällig den nächsten Befehl aus. Später in der for-Schleife kann die Vorhersage auf dem Verlauf basieren.
Für ein Array in aufsteigender Reihenfolge gibt es drei Möglichkeiten:
Alle Elemente sind kleiner als 128
Alle Elemente sind größer als 128
Einige neue Startelemente sind kleiner als 128 und später größer als 128
Nehmen wir an, dass der Prädiktor beim ersten Lauf immer den wahren Zweig annimmt.
Im ersten Fall wird es also immer das Wahre gebenverzweigen, da historisch alle seine Vorhersagen korrekt sind.
Im zweiten Fall wird zunächst eine falsche Vorhersage getroffen, nach einigen Iterationen jedoch eine korrekte Vorhersage.
Im dritten Fall wird es zunächst korrekt vorhergesagt, bis die Elemente kleiner als 128 sind. Danach wird es für einige Zeit fehlschlagen und sich selbst korrigieren, wenn es einen Fehler bei der Verzweigungsvorhersage in der Geschichte sieht.
In all diesen Fällen ist die Anzahl der Fehler zu gering. Infolgedessen müssen die teilweise ausgeführten Anweisungen nur einige Male verworfen und mit dem richtigen Zweig neu begonnen werden, was zu weniger CPU-Zyklen führt.
Im Fall eines zufälligen unsortierten Arrays muss die Vorhersage jedoch die teilweise ausgeführten Anweisungen verwerfen und die meiste Zeit mit der richtigen Verzweigung von vorne beginnen, was zu mehr CPU-Zyklen im Vergleich zum sortierten Array führt.
|
Eine offizielle Antwort wäre von
Intel - Vermeidung der Kosten für Branchenfehlvorhersagen
Intel - Reorganisation von Filialen und Schleifen zur Verhinderung von Fehlvorhersagen
Wissenschaftliche Arbeiten - Computerarchitektur zur Vorhersage von Zweigen
Bücher: J.L. Hennessy, D.A. Patterson: Computerarchitektur: ein quantitativer Ansatz
Artikel in wissenschaftlichen Publikationen: T.Y. Yeh, Y.N. Patt machte viele davon auf Branchenvorhersagen.
Sie können auch anhand dieses schönen Diagramms sehen, warum der Verzweigungsprädiktor verwirrt wird.
Jedes Element im Originalcode ist ein zufälliger Wert
Daten [c] = std :: rand ()% 256;
Der Prädiktor wechselt also die Seite, wenn std :: rand () bläst.
Auf der anderen Seite wird der Prädiktor, sobald er sortiert ist, zuerst in einen Zustand versetzt, in dem er stark nicht genommen ist, und wenn sich die Werte auf den hohen Wert ändern, ändert sich der Prädiktor in drei Durchläufen vollständig von stark nicht genommen zu stark genommen.
|
In derselben Zeile (ich denke, dies wurde durch keine Antwort hervorgehoben) ist es gut zu erwähnen, dass Sie manchmal (insbesondere in Software, in der die Leistung wichtig ist - wie im Linux-Kernel) einige if-Anweisungen wie die folgenden finden können:
if (wahrscheinlich (alles_ist_ok))
{
/* Etwas tun */
}}
oder ähnlich:
if (unwahrscheinlich (sehr unwahrscheinlicher Zustand))
{
/* Etwas tun */
}}
Sowohl wahrscheinlich () als auch unwahrscheinlich () sind tatsächlich Makros, die mithilfe von __builtin_expect des GCC definiert werden, um dem Compiler zu helfen, Vorhersagecode einzufügen, um die Bedingung unter Berücksichtigung der vom Benutzer bereitgestellten Informationen zu begünstigen. GCC unterstützt andere integrierte Funktionen, die das Verhalten des laufenden Programms ändern oder Anweisungen auf niedriger Ebene wie das Löschen des Caches usw. ausgeben können. In dieser Dokumentation werden die integrierten integrierten Funktionen des GCC beschrieben.
Normalerweise finden sich diese Optimierungen hauptsächlich in Echtzeitanwendungen oder eingebetteten Systemen, in denen die Ausführungszeit wichtig und kritisch ist. Wenn Sie beispielsweise nach einer Fehlerbedingung suchen, die nur 1/10000000 Mal auftritt, informieren Sie den Compiler darüber. Auf diese Weise würde die Verzweigungsvorhersage standardmäßig davon ausgehen, dass die Bedingung falsch ist.
|
Häufig verwendete Boolesche Operationen in C ++ erzeugen viele Zweige im kompilierten Programm. Wenn sich diese Zweige in Schleifen befinden und schwer vorherzusagen sind, können sie die Ausführung erheblich verlangsamen. Boolesche Variablen werden als 8-Bit-Ganzzahlen mit dem Wert 0 für false und 1 für true gespeichert.
Boolesche Variablen sind in dem Sinne überbestimmt, dass alle Operatoren, die Boolesche Variablen als Eingabe haben, prüfen, ob die Eingaben einen anderen Wert als 0 oder 1 haben, aber Operatoren, die Boolesche Werte als Ausgabe haben, keinen anderen Wert als 0 oder 1 erzeugen können Boolesche Variablen als Eingabe weniger effizient als nötig.
Betrachten Sie ein Beispiel:
Bool a, b, c, d;
c = a && b;
d = a || b;
Dies wird normalerweise vom Compiler folgendermaßen implementiert:
Bool a, b, c, d;
if (a! = 0) {
if (b! = 0) {
c = 1;
}}
sonst {
gehe zu CFALSE;
}}
}}
sonst {
CFALSE:
c = 0;
}}
if (a == 0) {
if (b == 0) {
d = 0;
}}
sonst {
gehe zu DTRUE;
}}
}}
sonst {
DTRUE:
d = 1;
}}
Dieser Code ist alles andere als optimal. Die Filialen können bei falschen Vorhersagen lange dauern. Die Booleschen Operationen können viel effizienter gestaltet werden, wenn mit Sicherheit bekannt ist, dass die Operanden keine anderen Werte als 0 und 1 haben. Der Grund, warum der Compiler keine solche Annahme macht, ist, dass die Variablen möglicherweise andere Werte haben, wenn sie nicht initialisiert sind oder aus unbekannten Quellen stammen. Der obige Code kann optimiert werden, wenn a und b mit gültigen Werten initialisiert wurden oder wenn sie von Operatoren stammen, die eine boolesche Ausgabe erzeugen. Der optimierte Code sieht folgendermaßen aus:
char a = 0, b = 1, c, d;
c = a & b;
d = a | b;
char wird anstelle von bool verwendet, um die Verwendung der bitweisen Operatoren (& und |) anstelle der booleschen Operatoren (&& und ||) zu ermöglichen. Die bitweisen Operatoren sind einzelne Befehle, die nur einen Taktzyklus benötigen. Der OR-Operator (|) funktioniert auch dann, wenn a und b andere Werte als 0 oder 1 haben. Der AND-Operator (&) und der EXCLUSIVE OR-Operator (^) können inkonsistente Ergebnisse liefern, wenn die Operanden andere Werte als 0 und 1 haben.
~ kann nicht für NOT verwendet werden. Stattdessen,Sie können einen Booleschen Wert NICHT für eine Variable festlegen, von der bekannt ist, dass sie 0 oder 1 ist, indem Sie sie mit 1 verknüpfen:
bool a, b;
b =! a;
kann optimiert werden für:
char a = 0, b;
b = a ^ 1;
a && b kann nicht durch a & b ersetzt werden, wenn b ein Ausdruck ist, der nicht ausgewertet werden sollte, wenn a falsch ist (&& wird b nicht bewerten, & wird). Ebenso ein || b kann nicht durch a | ersetzt werden b wenn b ein Ausdruck ist, der nicht ausgewertet werden sollte, wenn a wahr ist.
Die Verwendung bitweiser Operatoren ist vorteilhafter, wenn die Operanden Variablen sind, als wenn die Operanden Vergleiche sind:
bool a; doppeltes x, y, z;
a = x> y && z <5,0;
ist in den meisten Fällen optimal (es sei denn, Sie erwarten, dass der && -Ausdruck viele Verzweigungsfehler erzeugt).
|
Das ist sicher!...
Durch die Verzweigungsvorhersage wird die Logik langsamer ausgeführt, da in Ihrem Code umgeschaltet wird! Es ist, als ob Sie eine gerade Straße oder eine Straße mit vielen Abbiegungen fahren, sicher wird die gerade Straße schneller gemacht! ...
Wenn das Array sortiert ist, ist Ihre Bedingung im ersten Schritt falsch: data [c]> = 128, dann wird es ein wahrer Wert für den gesamten Weg bis zum Ende der Straße. So kommen Sie schneller zum Ende der Logik. Auf der anderen Seite müssen Sie bei Verwendung eines unsortierten Arrays viel drehen und verarbeiten, wodurch Ihr Code mit Sicherheit langsamer läuft ...
Schauen Sie sich das Bild an, das ich unten für Sie erstellt habe. Welche Straße wird schneller fertig?
Programmgesteuert führt die Verzweigungsvorhersage dazu, dass der Prozess langsamer wird ...
Auch am Ende ist es gut zu wissen, dass wir zwei Arten von Verzweigungsvorhersagen haben, die sich jeweils unterschiedlich auf Ihren Code auswirken werden:
1. Statisch
2. Dynamisch
Die statische Verzweigungsvorhersage wird vom Mikroprozessor zum ersten Mal verwendet
Es wird eine bedingte Verzweigung angetroffen und eine dynamische Verzweigungsvorhersage
wird für nachfolgende Ausführungen des bedingten Verzweigungscodes verwendet.
Um Ihren Code effektiv zu schreiben, um diese zu nutzen
Regeln sollten beim Schreiben von if-else- oder switch-Anweisungen am häufigsten überprüft werden
häufige Fälle zuerst und arbeiten schrittweise bis auf die am wenigsten verbreiteten.
Schleifen erfordern nicht unbedingt eine spezielle Reihenfolge des Codes für
statische Verzweigungsvorhersage, da nur die Bedingung des Schleifeniterators
wird normalerweise verwendet.
|
Diese Frage wurde bereits mehrfach hervorragend beantwortet. Trotzdem möchte ich die Aufmerksamkeit der Gruppe auf eine weitere interessante Analyse lenken.
Kürzlich wurde dieses Beispiel (geringfügig geändert) auch verwendet, um zu demonstrieren, wie ein Code innerhalb des Programms selbst unter Windows profiliert werden kann. Unterwegs zeigt der Autor auch, wie anhand der Ergebnisse ermittelt werden kann, wo der Code die meiste Zeit sowohl im sortierten als auch im unsortierten Fall verbringt. Schließlich zeigt das Stück auch, wie ein wenig bekanntes Merkmal der HAL (Hardware Abstraction Layer) verwendet wird, um zu bestimmen, wie viel Verzweigungsfehlvorhersage in dem unsortierten Fall auftritt.
Der Link ist hier:
Eine Demonstration der Selbstprofilierung
|
Wie bereits von anderen erwähnt, steckt hinter dem Rätsel der Branch Predictor.
Ich versuche nicht, etwas hinzuzufügen, sondern das Konzept auf andere Weise zu erklären.
Im Wiki gibt es eine kurze Einführung, die Text und Diagramme enthält.
Ich mag die folgende Erklärung, die ein Diagramm verwendet, um den Branch Predictor intuitiv zu erarbeiten.
In der Computerarchitektur ist ein Verzweigungsprädiktor a
digitale Schaltung, die versucht zu erraten, in welche Richtung ein Zweig (z
if-then-else-Struktur) wird gehen, bevor dies sicher bekannt ist. Das
Zweck des Verzweigungsprädiktors ist es, den Fluss in der zu verbessern
Anweisungspipeline. Zweigprädiktoren spielen eine entscheidende Rolle in
Erzielen einer hohen effektiven Leistung in vielen modernen Rohrleitungen
Mikroprozessorarchitekturen wie x86.
Die bidirektionale Verzweigung wird normalerweise mit einem bedingten Sprung implementiert
Anweisung. Ein bedingter Sprung kann entweder "nicht ausgeführt" werden und fortgesetzt werden
Ausführung mit dem ersten Codezweig, der unmittelbar folgt
nach dem bedingten Sprung, oder es kann "genommen" werden und zu einem springen
andere Stelle im Programmspeicher, wo sich der zweite Codezweig befindet
gelagert. Es ist nicht sicher bekannt, ob es sich um einen bedingten Sprung handelt
genommen oder nicht genommen, bis die Bedingung berechnet wurde und die
Der bedingte Sprung hat die Ausführungsphase in der Anweisung bestanden
Rohrleitung (siehe Abb. 1).
Basierend auf dem beschriebenen Szenario habe ich eine Animationsdemo geschrieben, um zu zeigen, wie Anweisungen in einer Pipeline in verschiedenen Situationen ausgeführt werden.
Ohne den Branch Predictor.
Ohne Verzweigungsvorhersage müsste der Prozessor bis zum warten
Der bedingte Sprungbefehl hat die Ausführungsphase vor dem
Der nächste Befehl kann in die Abrufphase der Pipeline eintreten.
Das Beispiel enthält drei Anweisungen und die erste ist eine bedingte Sprunganweisung. Die beiden letztgenannten Befehle können in die Pipeline aufgenommen werden, bis der bedingte Sprungbefehl ausgeführt wird.
Es dauert 9 Taktzyklen, bis 3 Anweisungen abgeschlossen sind.
Verwenden Sie Branch Predictor und machen Sie keinen bedingten Sprung. Nehmen wir an, dass die Vorhersage das nicht nimmtbedingter Sprung.
Es dauert 7 Taktzyklen, bis 3 Anweisungen abgeschlossen sind.
Verwenden Sie Branch Predictor und machen Sie einen bedingten Sprung. Nehmen wir an, dass die Vorhersage nicht den bedingten Sprung macht.
Es dauert 9 Taktzyklen, bis 3 Anweisungen abgeschlossen sind.
Die Zeit, die im Falle einer Verzweigungsfehlvorhersage verschwendet wird, ist gleich
die Anzahl der Stufen in der Pipeline von der Abrufstufe bis zur
Stufe ausführen. Moderne Mikroprozessoren haben in der Regel ziemlich lange
Pipelines, so dass die Fehlvorhersageverzögerung zwischen 10 und 20 Uhr liegt
Fahrräder. Infolgedessen erhöht die Verlängerung einer Pipeline den Bedarf an a
fortgeschrittener Zweigprädiktor.
Wie Sie sehen, haben wir anscheinend keinen Grund, Branch Predictor nicht zu verwenden.
Es ist eine recht einfache Demo, die den grundlegenden Teil von Branch Predictor verdeutlicht. Wenn diese Gifs ärgerlich sind, können Sie sie gerne aus der Antwort entfernen. Besucher können auch den Live-Demo-Quellcode von BranchPredictorDemo erhalten
|
Verzweigungsvorhersagegewinn!
Es ist wichtig zu verstehen, dass eine falsche Vorhersage von Zweigen Programme nicht verlangsamt. Die Kosten einer fehlenden Vorhersage sind so, als ob keine Verzweigungsvorhersage vorhanden wäre und Sie auf die Auswertung des Ausdrucks gewartet haben, um zu entscheiden, welcher Code ausgeführt werden soll (weitere Erläuterungen im nächsten Absatz).
if (Ausdruck)
{
// Führen Sie 1 aus
} else {
// Run 2
}}
Immer wenn es eine if-else \ switch-Anweisung gibt, muss der Ausdruck ausgewertet werden, um zu bestimmen, welcher Block ausgeführt werden soll. In den vom Compiler generierten Assemblycode werden Anweisungen für bedingte Verzweigungen eingefügt.
Ein Verzweigungsbefehl kann dazu führen, dass ein Computer mit der Ausführung einer anderen Befehlssequenz beginnt und somit von seinem Standardverhalten beim Ausführen von Befehlen in der Reihenfolge abweicht (dh wenn der Ausdruck falsch ist, überspringt das Programm den Code des if-Blocks), abhängig von einer Bedingung, die ist in unserem Fall die Ausdrucksbewertung.
Abgesehen davon versucht der Compiler, das Ergebnis vorherzusagen, bevor es tatsächlich ausgewertet wird. Es werden Anweisungen aus dem if-Block abgerufen, und wenn sich der Ausdruck als wahr herausstellt, dann wunderbar! Wir haben die Zeit für die Bewertung gewonnen und Fortschritte im Code erzielt. Wenn nicht, wird der falsche Code ausgeführt, die Pipeline wird geleert und der richtige Block wird ausgeführt.
Visualisierung:
Angenommen, Sie müssen Route 1 oder Route 2 auswählen. Während Sie darauf warten, dass Ihr Partner die Karte überprüft, haben Sie bei ## angehalten und gewartet, oder Sie können einfach Route1 auswählen und wenn Sie Glück haben (Route 1 ist die richtige Route). Dann war es großartig, dass Sie nicht darauf warten mussten, dass Ihr Partner die Karte überprüft (Sie haben die Zeit gespart, die er für die Überprüfung der Karte benötigt hätte), sonst kehren Sie einfach zurück.
Während das Spülen von Pipelines sehr schnell ist, lohnt es sich heutzutage, dieses Glücksspiel zu spielen. Das Vorhersagen sortierter Daten oder von Daten, die sich langsam ändern, ist immer einfacher und besser als das Vorhersagen schneller Änderungen.
O Route 1 / -------------------------------
/ | \ /
| --------- ## /
/ \ \
\.
Route 2 \ --------------------------------
|
In ARM ist keine Verzweigung erforderlich, da jeder Befehl über ein 4-Bit-Bedingungsfeld verfügt, das (zu Nullkosten) 16 verschiedene Bedingungen testet, die im Prozessorstatusregister auftreten können, und ob die Bedingung in einem Befehl vorliegt false, die Anweisung wird übersprungen. Dies macht kurze Verzweigungen überflüssig und es würde keinen Verzweigungsvorhersage-Treffer für diesen Algorithmus geben. Daher würde die sortierte Version dieses Algorithmus aufgrund des zusätzlichen Sortieraufwands langsamer als die unsortierte Version in ARM ausgeführt.
Die innere Schleife für diesen Algorithmus würde in der ARM-Assemblersprache ungefähr so ​​aussehen:
MOV R0, # 0 // R0 = sum = 0
MOV R1, # 0 // R1 = c = 0
ADR R2, Daten // R2 = Adresse des Datenarrays (diese Anweisung außerhalb der äußeren Schleife platzieren)
.inner_loop // Beschriftung der inneren Schleife
LDRB R3, [R2, R1] // R3 = Daten [c]
CMP R3, # 128 // vergleiche R3 mit 128
ADDGE R0, R0, R3 // wenn R3> = 128, dann Summe + = Daten [c] - kein Zweig erforderlich!
ADD R1, R1, # 1 // c ++
CMP R1, #arraySize // vergleiche c mit arraySize
BLT inner_loop // Verzweige zu inner_loop, wenn c  ());
für (vorzeichenloses c = 0; c  = 128
Summe = Summe + Daten1 (j);
Ende
Ende
Ende
toc;
ExeTimeWithSorting = toc - tic;
Die Ergebnisse für den obigen MATLAB-Code sind wie folgt:
a: Verstrichene Zeit (ohne Sortierung) = 3479,880861 Sekunden.
b: Verstrichene Zeit (mit Sortierung) = 2377,873098 Sekunden.
Die Ergebnisse des C-Codes wie in @GManNickG bekomme ich:
a: Verstrichene Zeit (ohne Sortierung) = 19,8761 Sek.
b: Verstrichene Zeit (mit Sortierung) = 7,377778 Sek.
Basierend darauf sieht es so aus, als ob MATLAB fast 175-mal langsamer als die C-Implementierung ohne Sortierung und 350-mal langsamer mit Sortierung ist. Mit anderen Worten, der Effekt (der Verzweigungsvorhersage) beträgt 1,46x für die MATLAB-Implementierung und 2,7x für die C-Implementierung.
|
Die Annahme durch andere Antworten, dass man die Daten sortieren muss, ist nicht korrekt.
Der folgende Code sortiert nicht das gesamte Array, sondern nur Segmente mit 200 Elementen und wird dabei am schnellsten ausgeführt.
Das Sortieren nur von Abschnitten mit k Elementen schließt die Vorverarbeitung in der linearen Zeit O (n) ab und nicht in der Zeit O (n.log (n)), die zum Sortieren des gesamten Arrays erforderlich ist.
#include 
#include 
#include 
int main () {
int data [32768]; const int l = Datengröße / Datengröße [0];
für (vorzeichenloses c = 0; c  = 128)
Summe + = Daten [c];
}}
}}
std :: cout << static_cast  (clock () - start) / CLOCKS_PER_SEC << std :: endl;
std :: cout << "sum =" << sum << std :: endl;
}}
Dies "beweist" auch, dass es nichts mit einem algorithmischen Problem wie der Sortierreihenfolge zu tun hat, und es ist in der Tat eine Verzweigungsvorhersage.
|
Bjarne Stroustrups Antwort auf diese Frage:
Das klingt nach einer Interviewfrage. Ist es wahr? Wie würdest du wissen? Es ist eine schlechte Idee, Fragen zur Effizienz zu beantworten, ohne vorher einige Messungen durchzuführen. Daher ist es wichtig zu wissen, wie man misst.
Also habe ich es mit einem Vektor von einer Million Ganzzahlen versucht und bekam:
Bereits 32995 Millisekunden sortiert
125944 Millisekunden gemischt
Bereits 18610 Millisekunden sortiert
133304 Millisekunden gemischt
Bereits 17942 Millisekunden sortiert
107858 Millisekunden gemischt
Ich habe das ein paar Mal gemacht, um sicher zu sein. Ja, das Phänomen ist real. Mein Schlüsselcode war:
void run (Vektor  & v, const string & label)
{
auto t0 = system_clock :: now ();
sort (v.begin (), v.end ());
auto t1 = system_clock :: now ();
cout << label
<< duration_cast  (t1 - t0) .count ()
<< "Millisekunden \ n";
}}
void tst ()
{
Vektor  v (1'000'000);
iota (v.begin (), v.end (), 0);
run (v, "bereits sortiert");
std :: shuffle (v.begin (), v.end (), std :: mt19937 {std :: random_device {} ()});
run (v, "gemischt");
}}
Zumindest ist das Phänomen bei diesen Einstellungen für Compiler, Standardbibliothek und Optimierer real. Unterschiedliche Implementierungen können und geben unterschiedliche Antworten. Tatsächlich hat jemand eine systematischere Studie durchgeführt (eine schnelle Websuche wird sie finden), und die meisten Implementierungen zeigen diesen Effekt.
Ein Grund ist die Verzweigungsvorhersage: Die Schlüsseloperation im Sortieralgorithmus lautet "if (v [i]  = 128. Das heißt, wir können leicht ein einzelnes Bit extrahieren, das uns sagt, ob wir einen Wert wollen oder nicht: durch Verschieben Bei den Daten rechts von 7 Bits bleibt ein 0-Bit oder ein 1-Bit übrig, und wir möchten den Wert nur hinzufügen, wenn wir ein 1-Bit haben. Nennen wir dieses Bit das "Entscheidungsbit".
Indem wir den 0/1-Wert des Entscheidungsbits als Index für ein Array verwenden, können wir Code erstellen, der gleich schnell ist, unabhängig davon, ob die Daten sortiert sind oder nicht. Unser Code fügt immer einen Wert hinzu, aber wenn das Entscheidungsbit 0 ist, fügen wir den Wert an einer Stelle hinzu, die uns egal ist. Hier ist der Code:
// Prüfung
clock_t start = clock ();
lang lang a [] = {0, 0};
lange lange Summe;
für (vorzeichenloses i = 0; i <100000; ++ i)
{
// Primärschleife
für (vorzeichenloses c = 0; c > 7);
a [j] + = Daten [c];
}}
}}
double elapsedTime = static_cast  (clock () - start) / CLOCKS_PER_SEC;
Summe = a [1];
Dieser Code verschwendet die Hälfte der Adds, hat jedoch nie einen Fehler bei der Verzweigungsvorhersage. Bei zufälligen Daten ist es enorm schneller als bei der Version mit einer tatsächlichen if-Anweisung.
In meinen Tests war eine explizite Nachschlagetabelle jedoch etwas schneller als diese, wahrscheinlich weil die Indizierung in eine Nachschlagetabelle etwas schneller war als die Bitverschiebung. Dies zeigt, wie mein Code die Nachschlagetabelle einrichtet und verwendet (im Code einfallslos lut für "LookUp Table" genannt). Hier ist der C ++ - Code:
// Deklariere und fülle dann die Nachschlagetabelle aus
int lut [256];
für (vorzeichenloses c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Verwenden Sie die Nachschlagetabelle, nachdem sie erstellt wurde
für (vorzeichenloses i = 0; i <100000; ++ i)
{
// Primärschleife
für (vorzeichenloses c = 0; c  Wert)
node = node-> pLeft;
sonst
node = node-> pRight;
Diese Bibliothek würde so etwas tun wie:
i = (x  Wert);
Knoten = Knoten-> Link [i];
Es ist eine schöne Lösung und vielleicht funktioniert es.
|
Sehr aktive Frage. Verdiene 10 Reputationen, um diese Frage zu beantworten. Die Reputationsanforderung schützt diese Frage vor Spam und nicht beantworteten Aktivitäten.
Nicht die Antwort, die Sie suchen? Durchsuchen Sie andere Fragen mit dem Tag "Java C ++ - Leistungsoptimierung" oder stellen Sie Ihre eigene Frage.